package problem144_Binary_Tree_Preorder_Traversal;

import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

import problem105_Construct_Binary_Tree_from_Preorder_and_Inorder_Traversal.MySolution.TreeNode;

public class SolutionNonRecursive {
	public List<Integer> preorderTraversal(TreeNode root) {
		List<Integer> result=new LinkedList<>();
		Stack<TreeNode> stack=new Stack<>();
		while(true){
			while(root!=null){
				result.add(root.val);
				stack.push(root);
				root=root.left;
			}
			if(stack.isEmpty())
				break;
			TreeNode curr=stack.pop();
			root=curr.right;
		}
		return result;
	}
}
